#include <cstdio>
#include <algorithm>
using namespace std;
long long arr[1000010];
int main(void){
    int n;
    arr[0]=1;
    arr[1]=1;
    for(int i=2;i<=1000000;i++){
        if(i%2==0){
            arr[i]=(arr[i-2]+arr[i/2])%1000000000;
        }
        else{
            arr[i]=arr[i-1]%1000000000;
        }
    }
    while(~scanf("%d",&n)){
        printf("%lld\n",arr[n]%1000000000);
    }
    return 0;
}